\documentclass{article}
\usepackage{mathtext}
\usepackage{cmap}
\usepackage[T1]{fontenc}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage[english,russian]{babel}
\usepackage[unicode,colorlinks=true, linkcolor=black]{hyperref}
\usepackage{tikz}
\usepackage{listings}
\usetikzlibrary{arrows,decorations.pathmorphing,backgrounds,positioning,fit}
\begin{document} 
\lstset{language=[Visual]C++}

\title{Подсистема управления памятью в приложении ShowGraph.\\Обоснование дизайна и внутреннее устройство.}
\author{Б. В. Шурыгин}
\date{2010г.}

\maketitle
\begin{abstract}
Данный документ описывает дизайн подсистемы памяти для приложения Showgraph.  Showgraph -- это система визуализации и редактирования направленных графов, а также визуализации компиляторного промежуточного представления. Система реализована на языке C++. В системе интенсивно используется набор библиотек Qt, который, однако не предоставляет подходящего менеджера памяти. В этой связи было принято решение реализовать подсистему управления памятью в минимальном виде, отвечающем требованиям проекта.
\end{abstract}

\tableofcontents
\section{Введение}
Подсистема управления памятью служит для решения нескольких проблем, связаных с динамическим выделением памяти. Т.к. в С++ забота об освобождении и выделении памяти ложится на программиста, то сопутствующие проблемы также должны решаться программистом. Ошибки при работе с памятью неизбежно возникают в процессе реализации крупных систем, следовательно архитектура системы должна с самого начала включать методы диагностики и борьбы с ними. Подсистема управления памятью, описываемая в данном документе не преследует целью устранить в корне какие либо возможности для возникновения ошибок управления памятью. Напротив, принимается как факт, что ошибки будут то и дело возникать и следует предпринять некоторые усилия чтобы диагностировать и устранять наиболее серьезные и часто встречающиеся ошибки. Итак, предпринимается попытка с помощью введения в программную систему отдельной компоненты, занимающейся выделением и исвобождением памяти свести к минимому количество ошибок выделения/освобождения памяти и влияние их на стабильность системы.

\section{Проблемы, связанные с динамическим выделением памяти}

Перечислим основные классы ошибок с которыми призвана бороться подсистема управления памятью.
\begin{enumerate}
\item  Указатель на удаленный объект -  т.н. «зависший» указатель

\item  Выделение памяти без освобождения, уничтожение последнего указателя на еще не освобожденную память  - утечка памяти 

\item  Фрагментация

\item  Низкая локальность обращений в память
\end{enumerate}
Кроме решения этих задач при подсистема управления памяти должна:

\begin{enumerate}
\item  Иметь простой интерфейс 

\item  Иметь низкие накладные расходы
\end{enumerate}

Обсудим подробнее каждую из проблем и перечисленные требования к подсистеме памяти.

\subsection{Зависшие  указатели}
Часто встречающаяся и трудная для воспроизведения, поиска и отладки ошибка. Суть ее в том, что при освобождении памяти могут оставаться указатели все еще показывающие на удаляемый объект. Попытка обращения по этим указателям после освобождения памяти может привести к сбою. Трудность поиска такой ошибки обусловлена трудностью ее воспроизведения, т.к. обращение по зависшему указателю может быть и успешным, если содежимое памяти после удаления еще не успело измениться. Кроме того, ошибка может проявляться не аварийным завершением, а просто непредсказуемым поведением программы.  Известные методы борьбы с ней состоят в следующем:

\begin{enumerate}
\item  Автоматический сборщик мусора. Если в программе каждый объект удаляется только сборщик мусора после того, как уничтожен последний указатель на него, то проблема перестает существовать (по крайней мере такая проблема редкость для систем с автоматическим освобождение памяти).

\item  Подсчет ссылок и проверка счетчика при освобождении
\end{enumerate}

В целом хороший дизайн системы и продуманая политика управления памятью также уменьшает вероятность таких ошибок. Например, последовательно проводимое разделение ответственности за выделяемую память между объектами.  По крайней мере удалять объект должен только другой объект, отвечающий за его память и располагающий возможность скорректировать все ссылки на удаляемую память.

\subsection{Утечка памяти}
Проблема состоит в том, что если выделять память, но не освобождать даже когда она больше не используется, то при долгой работе или обработке большого объема данных свободной памяти не останется. Важным частным случаем является потеря всех указателей на выделенную память, при этом ни освободить ни использовать ее будет уже нельзя. Такое случается, например, при удалении объекта содержащего единственный указатель на некоторый другой объект. В этом случае, если при удалении (например в деструкторе) первого объекта не удаляется второй, то удалить его дальше будет невозможно. Методы борьбы:

\begin{enumerate}
\item  Автоматический сборщик мусора

\item  Подсчет ссылок

\item  Локализация утечек с помощью пулов
\end{enumerate}

Полностью избавиться от утечек памяти с помощью этих средств вряд ли возможно. Трудность состоит в том, что пока сохраняется возможность адресовать объект, ни сборщик мусора, ни подсчет ссылок на объект не дают ответа на вопрос: будет ли этот объект использован в будущем?

\subsection{Фрагментация}
Под фрагментацией в данном документе понимается т.н. «внешняя» фрагментация. Проблема состоит в том, что при многократном выделении и освобождении памяти для небольших объектов, память как бы режется на кусочки (фрагменты, отсюда -- фрагментация). Т.е. в памяти лежат много небольших объектов, разделяющих свободные участки так, что для больших объектов просто невозможно выделять память. Традиционные решения:

\begin{enumerate}
\item  Использование перемещающего (копирующего) сборщика мусора
\item  Введение дополнительной косвенности для перемещения самих объектов с целью компактировки памяти
\item  Использование пулов для объектов одного размера
\end{enumerate}

\subsection{Низкая локальность обращений в память}
Под локальностью обращений в память здесь понимается мера того, на сколько часто близкие по времени обращения в память оказываются близкими по адресам. Низкая локальность обращений в память приводит к снижению производительности и неэффективной работе подсистемы память машины. Высокая локальность позволяет наиболее эффективно использовать кеш. Увеличить локальность можно с помощью пулов, либо с помощью сборщика мусора, отслеживающего и сравнивающего адреса обращений в память.

\section{Область применения и обоснование дизайна}
Описываемая подсистема памяти задумана как компонента системы визуализации промежуточного представления компиллятора. С этой точки зрения ее основные цели -- повышение надежности ключевых компонент системы, расширение возможностей отладки и увеличение производительности системы. Будем считать, что основное время система визуализации тратит на создание промежуточного представления и на расчет расположения вершин различных графов на плоскости. При этом в системе есть следующие основные классы объектов:

\begin{enumerate}
\item  Интерфейс пользователя (окна, кнопки, полосы прокрутки, панель инструментов, диалоги и т.п.) -- ожидается, что эта часть занимает мало пямяти, по сравнению с остальными

\item  Система отображения графа. Набор объектов соответствующих изображению вершин и дуг.

\item  Система отображения текста промежуточного представления

\item  Внутреннее представление различных графов. Вершины и дуги.
\end{enumerate}

Для отображения графа в системе используется набор классов из Qt. Важно здесь то, что хотя создание объектов рисования Qt доверяет клиенту библиотеки (т.е. нашей системе), после добавления элементов в сцену, их удалением распоряжается сцена. Сцена оперирует объектами через указатели. Для этих объектов можно выделить память, поддержать их высокую локальность, проследить чтобы все они были добавлены в сцену, а после удаления сцены -- удалены. Система отображения текста целиком основана на примитивах и классах работы с текстом библиотеки Qt. Выделение и освобождение памяти, занятой текстом происходит без непосредственного контроля программиста. Эти объекты нельзя будет контролировать с помощью нашего менеджера памяти. Наконец, внутреннее представление графа целиком подконтрольно нам и мы можем максимально свободно использовать любые средства для управления памятью, занимаемой дугами и вершинами.

Итак, при создании дизайна данной системы рассматривались следующие возможности:
\begin{enumerate}
\item  Использовать готовый сборщик мусора

\item  Реализовать минимально пригодный сборщик мусора самостоятельно

\item  Использовать готовые пулы памяти

\item  Реализовать собственные пулы памяти

\item  Использовать готовые «умные указатели»

\item  Реализовать собственные «умные указатели»
\end{enumerate}

\subsection{Сборщики мусора}
Сборщики мусора решают проблемы связаные с корректностью и даже иногда лучшают локальность ссылок. Однако известно, что они имеют нестабильную производительность и потребляют больше памяти. Выделение и освобождение памяти при использовании сборщика мусора только в самых простых случаях быстрее, чем стандартные \lstinline{malloc()/new}, \lstinline{free()/delete} методы. При работе с большим количеством долго живущих и сложно связанных объектов сборщики мусора испытывают сложности, т.к. рассчитаны на работу с небольшими изолированными объектами. Представление графа ( по крайней мере в текущей реализации ShowGraph) построено на связаных через указатели объектах типа «Узел» и «Дуга» (Node и Edge). Такая связанная в две стороны структура данных создает сложности для алгоритма, определяющего достижимы ли от root сегментов объекты графа. На практике же объекты графа обычно не нужны только после удаления графа целиком. Таким образом в наших условиях обход графа как структуры связанных объектов сборщиком мусора будет просто накладным расходом без реальной пользы. По указанным причинам от использования сборщика мусора ( как готового так и собственного) пришлось отказаться.

\subsection{Пулы памяти}
Пулы памяти ускоряют выделение и освобождение памяти. Пулы с фиксированным размером записи также сводят на нет фрагментацию и улучшают локальность. Пулы могут проверять при уничтожении освобождены ли все их объекты, что позволяет сигнализировать и достаточно хорошо изолировать утечку памяти. Пул может обнулить освобожденную память что поможет быстрее и точнее диагностировать зависшие указатели.  В нашем случае требуются именно пулы с фиксированным размером записи с проверками на удаление всех записей при уничтожении. При этом пул должен быть настраеваемым с возможностью отключения проверок в продуктовом режиме. Пул должен быть спроектирован так, чтобы классы использующие пул могли бы иметь наследников получающих свой аналогичный пул без дополнительных действий.

Существующие реализации, которые удалось найти, делятся на две категории -- учебные проекты, не позволяющие без доработки их использовать в нашей системе, и большие системы управления памятью, предоставляющие огромные возможности, большинство из которых вряд ли будет нами востребовано. Лишняя внешняя зависимость без весомой выгоды с одной стороны и достаточно простая реализация своего пула памяти с другой. В нашей системе выбор был сделан в пользу собственной разработки.

\subsection{Умные (интеллектуальные) указатели}
Интеллектуальный указатель (Smart pointer) -- объект, который можно использовать как указатель, но предоставляющий некоторые дополнительные функции. Одно из типичных применений -- организация счетчика ссылок. Проблема со счечиком ссылок в том, что существуют взаимные (или циклические) ссылки между объектами. В результате недостижимые программно объекты могут иметь ненулевые счетчики ссылок.

Учитывая, что автоматическое освобождение памяти не планируется, интеллектуальные указатели могут использоваться для проверок в отладочном режиме. В этом качестве они и приняты к реализации в системе Showgraph.

\section{Основные средства подсистемы памяти}
Итак, основными средствами управления памятью в нашей системе являются пулы с фиксированным размером записи и интеллектуальные указатели. Пулы отвечают за быстрое выделение и освобождение памяти. Кроме того в отладочном режиме пулы обнаруживают утечки памяти, выделенной с помощью них. Интеллектуальные указатели используются для реализации подсчета ссылок в отладочной версии. В рабочей версии они должны как можно ближе соответствовать обычным указателям.

По использованию средств контроля объекты разделяются на:
\begin{enumerate}
\item  Неконтроллируемые (raw)

\item  С контролем количества ссылок (ref count)

\item  С контролем занимаемой памяти (memory)

\item  С совместным контролем и ссылки и памяти (full)
\end{enumerate}
Соответственно контроль ссылок применяется для объектов, которые не участвуют в обмене данных с Qt-библиотеками, т.к. осуществляется через интеллектуальные указатели. Контроль выделения и освобождения памяти применяется для объектов созданных через пулы. Полностью контроль активизируется для объектов, выделяемых через пулы и снабженных интеллектуальными указателями.

Контролируемые ошибки для каждой группы:\\
\begin{tabular}{|p{1.9in}|p{0.6in}|p{0.8in}|p{0.8in}|} 
\hline & ref count & memory & full \\
\hline Утечка (простая потеря ссылок на объект)  & проверка & косвенно & проверка \\ 
\hline Утечка (образование циклических зависимостей)  &  & косвенно & косвенно \\
\hline Утечка (неосвобождение памяти)  &  & проверка & проверка \\
\hline Зависшие ссылки  & проверка & косвенно & проверка \\
\hline Фрагментация  &  & отсутствует & отсутсвует \\
\hline Нелокальность объектов &  & уменьшается & уменьшается \\ \hline
\end{tabular}\\

При отсутствии циклических зависимостей утечки памяти можно отслеживать с помощью счетчика ссылок. Однако гарантировать отсутствие таких зависимостей без анализа указателей в объектах система не может без реализации алгоритмов аналогичных анализу достижимости в сборщике мусора.  Тем не менее, для объектов размещеных в пуле отслеживаются любые не удаленные объекты. Это позволяет выявить (хотя и не в момент возникновения) объекты, на которые были утеряны ссылки, и объекты, участвующие в циклах ссылок. Для висячих ссылок на объекты в пуле можно также повысить вероятность критического сбоя обнулив память при удалении объекта.  

Для удобства отладки вводится счетчик событий, позволяющий по неудаленному объекту отследить момент его создания. При использовании интеллектуальных указателей можно хранить номера событий создания и удаления объекта. Объединив интеллектуальные указатели с событиями можно ввести для отладочного режима систему регистрации объектов, что позволит отслеживать создание и удаление любых объектов, даже тех, что не расположены в пуле.

\subsection{Интеллектуальные указатели}
Принятая в проекте стратегия работы с интеллектуальными указателями подразумевает, что мы не собираемся защищаться от намеренного некорректного использования указателей. Если программист действует в рамках принятых соглашений -- хорошо, он получит предупреждение, если ошибется. Если нарушает соглашения -- скорее всего не получит сообщения об ошибке. В частности, программист отвечает за то, чтобы объект полностью контролировался интеллектуальным указателем. Т.е. результат оператора \lstinline{new} не передавался никуда кроме конструктора интеллектуального указателя.

Для реализации подсчета ссылок используются 3 типа указателей: стандартный, обратный указатель и временный указатель. Стандарный указатель участвует в подсчете ссылок, а обратный и временный -- нет. Связи между объектами могут быть организованы любым образом, но при образовании циклических ссылок утечка памяти может остаться незамеченой. С учетом этого, в случае, если нужно ссылаться в две стороны лучше использовать обратный указатель для одной из ссылок.

\subsection{Пулы памяти}
Пулы памяти в проекте имеют один и тот же базовый интерфейс: они позволяют выделять некоторое количество памяти и удалять ранее выделенный участок памяти. Пулы памяти предназначены для выделения объектов поштучно, т.е. оператор \lstinline{new[]} для объектов в пуле использовать запрещается (как и \lstinline{delete[]}).
Общий интерфейс пула находится в прострастве имен \lstinline{Mem} и выглядит следующим образом:
\begin{lstlisting}
class Pool
{
    public:
        /** Allocate new memory block */
        virtual void* allocate( size_t size) = 0;
        /** Free memory block */
        virtual void deallocate( void *ptr) = 0;
        /** 
          * Functionality of 'operator delete'
          * for pooled objects
          */
        virtual void destroy( void *ptr) = 0;
};
\end{lstlisting}
Функция \lstinline{Pool::allocate} осуществляет выделение памяти, \lstinline{Pool::deallocate} осуществляет освобождение и \lstinline{Pool::destroy} служит для вызова деструктора объекта с последующим освобождением памяти. Для порождения классов, объекты которых можно размещать в пуле, служит класс \lstinline{PoolObj}.
\begin{lstlisting}
    /**
     * Base class for all objects allocated in pools
     */    
    class PoolObj
    {
    public:
        /** Default operator 'new' is disabled */
        void *operator new ( size_t size);
        /** Default operator 'delete' is disabled */
        void operator delete( void *ptr);
        /** Default operator 'new' is disabled */
        void *operator new[] ( size_t size);
        /** Default operator 'delete' is disabled */
        void operator delete[] ( void *ptr);
        
        /** Placement new */
        inline void *operator new ( size_t size, Pool* pool);
        /**
         * Operator 'delete' corresponding to placement new
         * WARNING: Compiler won't call this for deletion. 
         *          It is needed for freeing memory in  
         *          case of exceptions in constructor
         */
        inline void operator delete( void *ptr, Pool* pool);
        /** To be called by 'destroy' routine of pool class */
        virtual ~PoolObj(){};
    };
\end{lstlisting}
Чтобы создать объект некоторого класса в пуле, надо унаследовать его от \lstinline{PoolObj}. После этого ситаксис создания и удаления объектов следующий:
\begin{lstlisting}
class MyClass: public PoolObj
{
   /* Some useful code */        
};

void somefunc( Pool *pool)
{
    MyClass *ptr = new ( pool) MyClass();
    pool->destroy( ptr); // Calls destructor
}
\end{lstlisting}
\subsubsection{Пулы с фиксированным размером объекта}
Пул с фиксированным размером объекта пользуется знанием размера для упрощения внутренних структур и алгоритма выделения/освободения памяти. Это приводит к существенному ускорению по сравнению с пулами объектов, размер которых заранее не известен.

В проекте пулы фиксированного размера представлены шаблонными классами, производными от класса \lstinline{Pool}. В первую очередь рассмотрим класс \lstinline{FixedPool}.
\begin{lstlisting}
template < class Data> class FixedPool: public Pool
{
    /** Implementation... */
}
\end{lstlisting}
Параметр шаблона \lstinline{class Data} задает тип объектов для которых создается пул. Класс \lstinline{FixedPool} реализует 3 интерфейсные функции класса \lstinline{Pool}: \lstinline{allocate}, \lstinline{deallocate} и \lstinline{destroy}.

\end{document}
